1. Field of the Invention
The present invention relates to an image processing device and a method thereof, wherein, when carrying out pattern recognition on a digitalized image (fingerprints, stamped images, diagrams, letter characters, etc.) through use of an image processing device (hardware/software in a computer, an electronic switching machine a communication control unit, an IC card, an image recognition device, an image matching device, an image testing device, or the like), the image information for registration use is recorded in a memory device. This image processing device and the method thereof being further utilized to carry out a determination as to whether or not two images are identical through a comparison of the concordance (concordant match) between the two images.
2. Prior Art
The case where the image is a fingerprint will be presented as an example of an image on which pattern recognition is to be conducted. A fingerprint is the pattern of the ridges of a finger. Furthermore, because through valley lines (the space between the ridges) are set by ridges, in place of using a pattern showing ridges, it is acceptable to use a pattern showing through valley lines as the fingerprint. The lines treated as a fingerprint shall be called "fingerprint lines". There are a variety of fingerprint input devices for confirming an individual's identity, such as the method of input from an image pick-up device (for example, a CCD (charge coupled device) camera), the prism method (for example, Shimizu et al., "Entry Method of Fingerprint Image with Prism-Comparison between the Total Reflection Method and Light-Path Separation Method", IECE Journal, Vol. J68-D, No. 3, pp. 414-415 (1985)), and the hologram method (for example, Igaki, et al., "Personal Identification Terminal using Holographic Fingerprint Sensor", Institute of Electronics Information and Communication Engineers of Japan (IEICE) Technical Report, PRU 87-31, pp. 27-33, (1987)). The fingerprint image of analog information input from an image pick-up device is converted into a gray scale image of a digitized fingerprint by an analog/digital converter. This gray scale image of the fingerprint is indicated by coordinate (X,Y), which is the image memory pixel address, and by the brightness of the pixels, which is a component of each pixel address of image memory. The scheme of setting the X and Y axes is freely chosen. A fingerprint image may be formed by converting the concavities and convexities of the fingerprint directly into a binary image. Correction can then be carried out on the gray scale image of the fingerprint according to smoothing and using the direction of the ridges. End points, branch points and points of intersection are present as characteristic points that show the distinctive features of a fingerprint. The characteristic points of the gray scale image of a digitalized fingerprint can be detected by binarizing a fingerprint image, further thinning it and then detecting whether a pattern identical to the pattern of a region of pixels showing a characteristic point is present in the thinned image (for example, Sasagawa et al., "Personal Verification System with High Tolerance of Poor Quality Fingerprints", IEICE Journal, Vol. J72-D-II, No. 5, pp. 707-714 (1989)).
In a fingerprint comparison, the fingerprint for which information has been recorded in memory prior to the time of comparison is called a "registered fingerprint". The fingerprint which is compared for similarity to the registered fingerprint is called a "tested fingerprint". Known methods for comparing a registered fingerprint to a tested fingerprint includes: a method of utilizing the characteristic points of the fingerprint, a method of utilizing the direction of the ridges, and a method of matching the patterns of the original images of the tested fingerprint to that of the registered fingerprint. Japanese Patent Application, First Publication, Laid Open No. Sho 63-132386 discloses a comparison method relying on the superimposition of a thinned image of the tested fingerprint and a thinned image of the registered fingerprint as a method of pattern matching of thinned images.
Smoothing, a treatment for decreasing the noise of a fingerprint image, is, for example, recorded in "Handbook of Image Analysis", pp. 538-548, Tokyo University Publishing (1991), Takagi and Shimoda (Eds.), in which there is a local summation averaging filter which uses the values of neighboring pixels of each pixel.
In the thinning process of a binary image, for those pixels which constitute a line, a majority (majority means from more than half to all, ideally all) of the line widths are set to a width of one pixel. Each pixel of each line may be either black or white. In the description which follows however, the case where each pixel of each line is black will be described. Hilditch's thinning method, in which the outer black pixels in a black pixel aggregation are sequentially deleted while the connectivity between black pixels is maintained, is available, among others, as a method of binarizing a gray scale image and carrying out thinning on that binary image. (See, example, "Introduction to Computer Image Processing", Tamura (Ed.), Soken-Shuppan, pp. 80-83 (1985); Tamura, "Research Related to Multi-sided Image Processing and Its Software", Electrotechnical Laboratory in Japan (ETL), Research Report, pp. 25-64, No. 835 (February, 1984); and Mori et al., "Fundamentals of Image Recognition [I]", pp. 65-71, Ohm Corporation (1986)). In Kobayashi, "A Thinning Method for Extracting Characteristic Points from an Image", IEICE (Institute of Electronics, Information and Communication Engineers of Japan) Technical Report, PRU 90-149, pp. 33-38 (1991), a method of thinning a gray scale image or a binary image is disclosed. As for connectivity between black pixels, either 4-neighbor connected or 8-neighbor connected is used. Four-neighbor connected and 8-neighbor connected are also called 4-connected and 8-connected (e.g., "Introduction to Computer Image Processing", Tamura (Ed.), Soken-Shuppan, pp. 70, (1985)).
A method of creating a binary image by binarizing a light/dark image is disclosed among others, for example, in Mori et al., "Fundamentals of Image Recognition [I]", pp. 65-71, Ohm Corporation (1986).
In the input of a fingerprint, because errors in recognition (rotation and/or parallel displacement) of the tested fingerprint and the registered fingerprint occur, it is necessary to carry out positioning of both fingerprints when performing a comparison between a tested fingerprint and a registered fingerprint. As a method of position matching (rotation, vertical and horizontal displacements), a method utilizing the ridge direction, a method according to representative characteristic points and neighboring characteristic points, and a method of trial and error of displacing in parallel only the movable area are known as methods to position set the image so that the greatest degree of concordance is achieved. A conventional method for performing the coordinate transformation and the geometric transformation necessary when carrying out position matching is disclosed in, for example, Plastock et al., translated by Koriyama, "Theory and Problems of Computer Graphics", pp. 84-88, McGraw Hill Inc. (1987).
In the position matching during an image comparison, it is useful to obtain the approximate center point of the fingerprint image. Japanese Patent Application, Second Publication, Laid Open No. Sho 58-55548 "A Method for Determining the Center Position of a Figure" discloses a method in which the ridges having gradients of sudden increase are investigated one by one, to obtain the center point. In Ito et al., "An Algorithm for Classification of Fingerprints Based on the Core", IEICE Technical Report, PRU 89-79, pp. 15-22 (1989) a method is disclosed of utilizing the parallel lines of each rectangular area and the number of intersections to approach the center points one by one. In "An Extraction Technique of the Pivot Location for Automated Fingerprint Identification Process", IEICE National Conference on Information and Systems, No. 125, (1987), the number of ridges passing through each scanning line is calculated and the distribution of the number of lines is obtained.
Kobayashi, "A Template Matching Scheme for Fingerprint Image Recognition", IEICE Technical Report, PRU 91-45 and the IEICE Journal, pp. 25-30 (July, 1991), show a method according to the template matching of the black pixels obtained from the thinned line image of a registered fingerprint (or an image on which narrowization has been performed) to the binary image (or an image on which narrowization has been performed). In this method, the quantity of processing and the quantity of memory are decreased more than in a method carrying out template matching utilizing binary images. Narrowization means to reduce the line width of an image. Thinning means to reduce the line width of an image to 1 pixel. Thinning is a special case of narrowization.
In the memory conservation of registered information, it is necessary to make the quantity of memory as small as possible. In the present invention, it is necessary to memory store as registered information a binary image which has undergone narrowization processing. As a method of memory storing line figures, Freeman's method according to chain symbols (i.e., Yasuiin and Nakajima, "Image Information Processing", pp. 113-114, Morikita Publishing (1991)) is known. However, the application of this method to a case where the image is a complicated one, as in the case of a fingerprint image, is difficult.